#ifndef BIGINT_HPP
#define BIGINT_HPP
#ifdef __AVX2__
#include <immintrin.h>
#endif
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
namespace myh {
    class BigInt {
    private:
        bool sign;
        std::vector<int> digits;
        static constexpr int BASE=100000000;
        static constexpr int BASE_DIGITS=8;
        static constexpr long long P=998244353;
        static constexpr long long g=3;
        void normalize() {
            auto rit=std::find_if(digits.rbegin(),digits.rend(),[](int v){return v!=0;});
            digits.erase(rit.base(),digits.end());
            if(digits.empty()) digits.push_back(0);
        }
        static long long powMod(long long base,long long exp,long long mod) {
            base%=mod;
            long long result=1;
            while(exp>0) {
                if(exp&1) result=(result*base)%mod;
                base=(base*base)%mod;
                exp>>=1;
            }
            return result;
        }
        static void ntt(std::vector<long long>& a,bool inverse = false) {
            size_t n=a.size();
            for (size_t i=1,j=0;i<n;i++) {
                size_t bit=n>>1;
                for(;j&bit;bit>>=1) j^=bit;
                j^=bit;
                if(i<j) std::swap(a[i],a[j]);
            }
            for(size_t len=2;len<=n;len<<=1) {
                long long wn=powMod(g,(P-1)/len,P);
                if(inverse) wn=powMod(wn,P-2,P);
                for(size_t i=0;i<n;i+=len) {
                    long long w=1;
                    for(size_t j=0;j<len/2;j++) {
                        size_t idx1=i+j,idx2=i+j+len/2;
                        long long u=a[idx1],v=a[idx2]*w%P;
                        a[idx1]=(u+v)%P,a[idx2]=(u-v+P)%P,w=w*wn%P;
                    }
                }
            }
            if(inverse) {
                long long inv_n=powMod(n,P-2,P);
                for(size_t i=0;i<n;i++) a[i]=a[i]*inv_n%P;
            }
        }
        static std::vector<int> nttMultiply(const std::vector<int>& a,const std::vector<int>& b) {
            size_t len_a=a.size(),len_b=b.size(),n=1;
            while(n<len_a+len_b) n<<=1;
            std::vector<long long> fa(n,0),fb(n,0);
            for(size_t i=0;i<len_a;i++) fa[i]=a[i];
            for(size_t i=0;i<len_b;i++) fb[i]=b[i];
            ntt(fa,false);
            ntt(fb,false);
            for(size_t i=0;i<n;i++) fa[i]=fa[i]*fb[i]%P;
            ntt(fa,true);
            std::vector<int> result(n);
            for(size_t i=0;i<n;i++) result[i]=static_cast<int>(fa[i]);
            return result;
        }
        BigInt getLower(size_t m) const {
            if(m>=digits.size()) return *this;
            BigInt result;result.sign=true;
            result.digits=std::vector<int>(digits.begin(),digits.begin()+m);
            result.normalize();return result;
        };
        BigInt getUpper(size_t m) const {
            if(m>=digits.size()) return BigInt(0);
            BigInt result;result.sign=true;
            result.digits=std::vector<int>(digits.begin()+m,digits.end());
            result.normalize();return result;
        };
        static BigInt karatsubaMultiply(const BigInt& x, const BigInt& y) {
            size_t n = std::max(x.digits.size(), y.digits.size());
            if(n <= 32) return x.naiveMultiply(y);
            size_t m=(n+1)/2;
            BigInt low1=x.getLower(m),low2=y.getLower(m),high1=x.getUpper(m),high2=y.getUpper(m);
            BigInt z0=karatsubaMultiply(low1,low2);
            BigInt z1=karatsubaMultiply(high1,high2);
            BigInt middle=karatsubaMultiply(low1+high1,low2+high2)-z1-z0;
            auto shiftLeft=[](BigInt& i,size_t n){
                if(i==0) return;i.digits.insert(i.digits.begin(),n,0);
            };
            shiftLeft(z1,2*m);
            shiftLeft(middle,m);
            return z1+middle+z0;
        }
        BigInt simdSubtract(const BigInt& a,const BigInt& b) const {
            BigInt res=a,b2=b;
            if(res.digits.size()!=b2.digits.size()){
                bool flag=res.digits.size()>b2.digits.size();
                (flag?b2:res).digits.resize((flag?res.digits.size():b2.digits.size()));
            }
            #ifdef __AVX2__
            while(res.digits.size()%8) res.digits.push_back(0);
            while(b2.digits.size()%8) b2.digits.push_back(0);
            int* a_digits=res.digits.data();
            const int* b_digits=b2.digits.data();
            for(size_t i=0;i<res.digits.size();i+=8) {
                __m256i va=_mm256_loadu_si256((__m256i*)(a_digits+i));
                __m256i vb=_mm256_loadu_si256((__m256i*)(b_digits+i));
                __m256i vres=_mm256_sub_epi32(va,vb);
                _mm256_storeu_si256((__m256i*)(a_digits+i),vres);
            }
            #else
            int* a_digits=res.digits.data();
            const int* b_digits=b2.digits.data();
            for(size_t i=0;i<b2.digits.size();++i) a_digits[i]-=b_digits[i];
            #endif
            int borrow=0;
            for(auto& d:res.digits) {
                int temp=d-borrow;
                borrow=(temp<0)?1:0;
                d=(temp+BASE)%BASE;
            }
            res.normalize();
            return res;
        }
        BigInt naiveMultiply(const BigInt& other) const {
            BigInt result;
            result.sign=true;
            result.digits.resize(digits.size()+other.digits.size(), 0);
            for(size_t i=0;i<digits.size();i++) {
                long long carry = 0;
                for (size_t j = 0; j < other.digits.size() || carry; j++) {
                    long long product=result.digits[i+j]+static_cast<long long>(digits[i])*
                                      (j<other.digits.size()?other.digits[j]:0)+carry;
                    carry=product/BASE;
                    result.digits[i+j]=static_cast<int>(product%BASE);
                }
            }
            result.normalize();
            return result;
        }
        static void fastDivision(const BigInt& dividend, const BigInt& divisor, BigInt& quotient, BigInt& remainder) {
            if(divisor==0) throw std::runtime_error("Divide by zero");
            if(dividend==divisor) quotient=1,remainder=0;
            BigInt absDividend=dividend.abs();
            BigInt absDivisor=divisor.abs();
            if(absDividend==0||absDividend<absDivisor) {
                quotient=0,remainder=dividend;
                return;
            }
            quotient.digits.clear();
            remainder=0;
            BigInt mulyiplrs[10];
            mulyiplrs[0]=0;
            for(int i=1;i<=9;++i) mulyiplrs[i]=absDivisor*i;
            for(int i=absDividend.digits.size()-1; i>=0; i--) {
                remainder=remainder*BASE+absDividend.digits[i];
                int q=0,l=0,r=9;
                while(l<r){
                    int mid=(l+r)/2;
                    if(remainder>=mulyiplrs[mid]) q=mid,l=mid+1;
                    else r=mid-1;
                }
                remainder-=mulyiplrs[q];
                BigInt tempDivisor=absDivisor;
                while(remainder>=tempDivisor) remainder-=tempDivisor,q++;
                quotient.digits.insert(quotient.digits.begin(),q);
            }
            quotient.sign=(dividend.sign==divisor.sign);
            quotient.normalize();
            remainder.sign=dividend.sign;
            remainder.normalize();
        }
    public:
        BigInt() : sign(true), digits{0} {}
        BigInt(long long num) {
            if (num == 0) {
                sign = true;
                digits = {0};
                return;
            }
            sign = (num >= 0);
            num = std::abs(num);
            while (num > 0) {
                digits.push_back(num % BASE);
                num /= BASE;
            }
        }
        BigInt(const std::string& numStr) {
            if (numStr.empty()) {
                sign = true;
                digits = {0};
                return;
            }
            size_t start = 0;
            if (numStr[0] == '-') {
                sign = false;
                start = 1;
            } else if (numStr[0] == '+') {
                sign = true;
                start = 1;
            } else sign = true;
            while(start < numStr.size() && numStr[start] == '0')  start++;
            if (start == numStr.size()) {
                sign = true;
                digits = {0};
                return;
            }
            int pos = numStr.size() - 1;
            while (pos >= static_cast<int>(start)) {
                int digit = 0,power = 1;
                for(int i = 0; i < BASE_DIGITS && pos >= static_cast<int>(start); i++) {
                    if(!std::isdigit(numStr[pos]))
                        throw std::invalid_argument("Invalid character in number string");
                    digit+=(numStr[pos]-'0')*power,power *= 10,pos--;
                }
                digits.push_back(digit);
            }
            normalize();
        }
        BigInt(const BigInt& other) = default;
        BigInt& operator=(const BigInt& other) = default;
        BigInt operator-() const {
            BigInt result = *this;
            if (result != BigInt(0)) 
                result.sign = !result.sign;
            return result;
        }
        BigInt operator+(const BigInt& other) const {
            if(sign!=other.sign) return sign?*this-(-other):other-(-*this);
            BigInt result=*this,b2=other;
            if(result.digits.size()!=b2.digits.size()){
                bool flag=result.digits.size()>b2.digits.size();
                (flag?b2:result).digits.resize((flag?result.digits.size():b2.digits.size()),0);
            }
            #ifdef __AVX2__
            while(result.digits.size()%8) result.digits.push_back(0);
            while(b2.digits.size()%8) b2.digits.push_back(0);
            size_t asize=result.digits.size();
            int* a_digits=result.digits.data(),*b_digits=b2.digits.data();
            for(size_t i=0;i<asize;i+=8){
                __m256i va=_mm256_loadu_si256((__m256i*)a_digits+i);
                __m256i vb=_mm256_loadu_si256((__m256i*)b_digits+i);
                _mm256_storeu_si256((__m256i*)(a_digits+i),_mm256_add_epi32(va,vb));
            }
            #else
            result.sign=sign;
            size_t asize=result.digits.size();
            for (size_t i=0;i<asize;i++) result.digits[i]+=b2.digits[i];
            #endif
            int carry=0;
            for(size_t i=0;i<asize;i++){
                int sum=result.digits[i]+carry;
                result.digits[i]=sum%BASE;
                carry=sum/BASE;
            }
            result.normalize();
            if(result.digits.size()==0) result.digits.push_back(0);
            return result;
        }
        BigInt operator-(const BigInt& other) const {
            if(sign!=other.sign) return *this+(-other);
            BigInt res;
            if(sign) res=(*this>=other)?simdSubtract(*this,other):-simdSubtract(other,*this);
            else res=(*this<=other)?simdSubtract(-*this,-other):-simdSubtract(-other,-*this);
            if(res!=BigInt(0)&&res.sign) while(res.digits.front()==0) res.digits.erase(res.digits.begin());
            return res;
        }
        BigInt operator*(const BigInt& other) const {
            if(*this == 0 || other == 0) return BigInt(0);
            bool resultSign = (sign == other.sign);
            BigInt absThis = abs();
            BigInt absOther = other.abs();
            size_t len1 = absThis.digits.size();
            size_t len2 = absOther.digits.size();
            if(len1 <= 32 || len2 <= 32)
                return absThis.naiveMultiply(absOther).withSign(resultSign);
            else if(len1 <= 1024 && len2 <= 1024)
                return karatsubaMultiply(absThis, absOther).withSign(resultSign);
            else {
                std::vector<int> a_digits = absThis.digits;
                std::vector<int> b_digits = absOther.digits;
                std::vector<int> result_digits = nttMultiply(a_digits, b_digits);
                BigInt result;
                result.sign = true;
                long long carry = 0;
                for (int digit : result_digits) {
                    long long total = static_cast<long long>(digit) + carry;
                    carry = total / BASE;
                    result.digits.push_back(static_cast<int>(total % BASE));
                }
                while (carry) {
                    result.digits.push_back(static_cast<int>(carry % BASE));
                    carry /= BASE;
                }
                result.normalize();
                return result.withSign(resultSign);
            }
        }
        BigInt operator/(const BigInt& divisor) const {
            BigInt quotient, remainder;
            fastDivision(*this, divisor, quotient, remainder);
            return quotient;
        }
        BigInt operator%(const BigInt& divisor) const {
            BigInt quotient, remainder;
            fastDivision(*this, divisor, quotient, remainder);
            return remainder;
        }
        BigInt& operator+=(const BigInt& other) { *this = *this + other; return *this; }
        BigInt& operator-=(const BigInt& other) { *this = *this - other; return *this; }
        BigInt& operator*=(const BigInt& other) { *this = *this * other; return *this; }
        BigInt& operator/=(const BigInt& other) { *this = *this / other; return *this; }
        BigInt& operator%=(const BigInt& other) { *this = *this % other; return *this; }
        BigInt& operator++() { *this += 1; return *this; }
        BigInt operator++(int) { BigInt tmp = *this; ++*this; return tmp; }
        BigInt& operator--() { *this -= 1; return *this; }
        BigInt operator--(int) { BigInt tmp = *this; --*this; return tmp; }
        bool operator==(const BigInt& other) const {
            return sign == other.sign && digits == other.digits;
        }
        bool operator!=(const BigInt& other) const { return !(*this == other); }
        bool operator<(const BigInt& other) const {
            if(sign != other.sign) 
                return !sign;
            if(digits.size() != other.digits.size())
                return sign ? (digits.size() < other.digits.size()) : (digits.size() > other.digits.size());
            for(int i = digits.size() - 1; i >= 0; i--)
                if(digits[i] != other.digits[i])
                    return sign ? (digits[i] < other.digits[i]) : (digits[i] > other.digits[i]);
            return false;
        }
        bool operator>(const BigInt& other) const { return other < *this; }
        bool operator<=(const BigInt& other) const { return !(*this > other); }
        bool operator>=(const BigInt& other) const { return !(other > *this); }
        BigInt operator<<(size_t shift) const {
            if (*this == 0) return *this;
            BigInt result = *this;
            size_t blockShift = shift / BASE_DIGITS;
            size_t digitShift = shift % BASE_DIGITS;
            if(blockShift > 0)
                result.digits.insert(result.digits.begin(), blockShift, 0);
            if(digitShift > 0) {
                long long carry = 0;
                long long multiplier = std::pow(10, digitShift);
                for(size_t i = 0; i < result.digits.size(); i++) {
                    long long val = static_cast<long long>(result.digits[i]) * multiplier + carry;
                    carry = val / BASE;
                    result.digits[i] = static_cast<int>(val % BASE);
                }
                if(carry > 0) result.digits.push_back(static_cast<int>(carry));
            }
            result.normalize();
            return result;
        }
        BigInt operator>>(size_t shift) const {
            if (shift == 0) return *this;
            BigInt result = *this;
            size_t blockShift = shift / BASE_DIGITS;
            size_t digitShift = shift % BASE_DIGITS;
            if(blockShift >= result.digits.size()) return BigInt(0);
            if(blockShift>0) result.digits.erase(result.digits.begin(), result.digits.begin() + blockShift);
            if(digitShift>0) {
                long long divisor=std::pow(10,digitShift);
                long long carry=0;
                for (int i = result.digits.size() - 1; i >= 0; i--) {
                    long long val = carry * BASE + result.digits[i];
                    result.digits[i] = static_cast<int>(val / divisor);
                    carry = val % divisor;
                }
            }
            result.normalize();
            return result;
        }
        BigInt abs() const {
            BigInt result = *this;
            result.sign = true;
            return result;
        }
        BigInt withSign(bool newSign) const {
            BigInt result = *this;
            if(result != BigInt(0)) result.sign=newSign;
            return result;
        }
        bool isOdd() const {
            if (digits.empty()) return false;
            return (digits[0] & 1) != 0;
        }
        BigInt pow(const BigInt& exponent) const {
            if (exponent == 0) {
                if (*this == 0) return BigInt(1);
                return BigInt(1);
            }
            if (*this == 0) {
                if (exponent.sign) return BigInt(0);
                throw std::runtime_error("Zero to negative power undefined");
            }
            if(!exponent.sign)
                throw std::runtime_error("Negative exponents not supported for integers");
            bool resultSign = false;
            if(!sign && exponent.isOdd())
                resultSign = true;
            BigInt absResult = abs().powCore(exponent);
            return absResult.withSign(resultSign);
        }
        friend std::ostream& operator<<(std::ostream& os, const BigInt& num) {
            if(!num.sign && num != BigInt(0)) os << '-';
            if(num.digits.empty()) os << '0';
            else {
                os << num.digits.back();
                for(int i = static_cast<int>(num.digits.size()) - 2; i >= 0; i--)
                    os << std::setw(BASE_DIGITS) << std::setfill('0') << num.digits[i];
            }
            return os;
        }
        friend std::istream& operator>>(std::istream& is, BigInt& num) {
            std::string str;
            is >> str;
            try {
                num = BigInt(str);
            } catch(...) {
                is.setstate(std::ios::failbit);
                num = BigInt(0);
            }
            return is;
        }
        BigInt powCore(const BigInt& exponent) const {
            if (exponent == 0) return BigInt(1);
            if (*this == 1) return BigInt(1);
            if (*this == -1) return exponent.isOdd() ? BigInt(-1) : BigInt(1);
            BigInt base = *this;
            BigInt exp = exponent;
            BigInt result(1);
            while (exp != 0) {
                if(exp.isOdd()) result = result * base;
                base = base * base;
                exp.divideByTwo();
            }
            return result;
        }
        void divideByTwo() {
            if(digits.empty()) return;
            long long carry = 0;
            for (int i = static_cast<int>(digits.size()) - 1; i >= 0; i--) {
                long long num = carry * BASE + digits[i];
                digits[i] = static_cast<int>(num / 2);
                carry = num % 2;
            }
            normalize();
        }
        friend class BigFloat;
    };
    template<std::integral T>
    T gcd(T a,T b){
        int tmp;
        while(b!=0){
            tmp=a%b;
            a=b;
            b=tmp;
        }
        return a;
    }
    template<std::integral T>
    T lcm(T a,T b){
        return a/gcd(a,b)*b;
    }
    BigInt gcd(BigInt a,BigInt b){
        BigInt tmp=a;
        while(b!=0){
            tmp=b;
            b=a%b;
            a=tmp;
        }
        return a;
    }
    BigInt lcm(BigInt a,BigInt b){
        return a/gcd(a,b)*b;
    }
}
#endif